There are loopholes in the method
The same, here no slop generated by ai, written by hand instead.
I managed to solve one round in Google Kick Start in one week, and it makes me feel fulfilled and it keeps my coding level in the vibe coding era.
Why is this one titled "There are loopholes in the method"? You must be wondering.
Yes, I designed it to attract your eyesight but that's not the only reason, it comes from the real experience while I was solving these problems, including the confusing part.
To put it simply, it is because that we can hardly think it through within a 5-min brain storm. There will almost always be leakings.
That's my personal idea after all and you may possibly finish it at the first round of consideration possibly, I know you are definitely not beginners like me.
The same is to rank them at the difficulty:
1. Alien Generator
2. Smaller Strings
3. Rock Paper Scissors
4. Binary Operator
Alien Generator
This is almost the simplest one I've ever met.
You can go instinctively. You can simply travel through all the possible days and check if there are possible positive integer $K$ matches this formula:
$$K \cdot N = G - \frac{N(N - 1)}{2}$$if this gets legal, add one to counter.
And we can induct the formula to:
$$2 \cdot K = \frac{2G}{N} - N + 1$$In that case: you have to check two things:
1. $2G$ must be divisible by $N$
2. $\frac{2G}{N} - N + 1$ must be divisible by $2$
Despite that $N$ can reach $10^{12}$, with the prerequisite $N \cdot (N - 1) < 2 \cdot G$ (equaling are not allowed cause $K$ is required to be positive), code can pass the Time limit easily.
Anyway, my code here:
#include <iostream>
#include <vector>
#define int long long
void solve() {
int G;
std::cin >> G;
int N = 1;
int cnt = 0;
while(N * (N - 1) < 2 * G) {
if((2 * G) % N == 0 && ((2 * G) / N - N + 1) % 2 == 0) {
cnt++;
}
N++;
}
std::cout << cnt << "\n";
}
signed main () {
int T;
std::cin >> T;
for (int i = 1;i <= T;i++) {
std::cout << "Case #" << i << ": ";
solve();
}
return 0;
}
It seems that there are always loopholes while coding and you can hardly think through at the first insight.
Smaller Strings
Despite that it is ranked in the 3rd place, it is not easy.
How to say that? You may still forget something to code, some hidden cases for example.
No redundant review of the statement of the problems. Let's begin anyway.
We are told to find all the string that is smaller than the targeting string and palindrome. But with a given length $\mathbf{N}$, the palindrome string depends only on the first half, namely $\mathbf{[1,\lceil\frac{N}{2}\rceil]}$. Now focus on the targeting string $\mathbf{S}$, it also works as a limiting string. Now switch to all the char before the last char in the first half. If you set one of them to the char smaller than what was originally put in that place, then the char after can be any char within a $K$ range.
That is: for char indexed at i, it contributes totally $$\mathbf{K^{boundary\_index - i - 1} \cdot (str[i] - a(ASCII))}$$ choices, the same to every one of them. Now back to the boundary char, whether the palindrome can equal it or not need special check like:
We need to check what if we set this char to the same as targeting string $\mathbf{S}$. Will the palindrome be bigger than $\mathbf{S}$? That's the question we got to answer.
And check is easy, just follow the basic rules of comparing strings.
Code here:
#include <iostream>
#define int long long
const long long MOD = 1e9 + 7;
int pow(int a,int b) {
int x = 1;
while(b) {
if(b & 1) {
x = (x * a) % MOD;
}
b >>= 1;a = a * a % MOD;
}
return x;
}
void solve() {
int N;
int K;
std::cin >> N >> K;
std::string s;
std::cin >> s;
s = "#" + s;
if(N == 1) {
std::cout << s[1] - 'a' << "\n";
return ;
}
int M = (N + 1)/ 2;
//1-indexed here
std::string new_s = "#";
for (int i = 1;i < M;i++) {
new_s += s[i];
}
bool can_equal = true;
int cnt = 0;
for (int i = M + 1;i <= N;i++) {
if(s[i] < s[N + 1 - i]) {
can_equal = false;
break;
} else if (s[i] > s[N + 1 - i]) {
can_equal = true;
break;
} else if (s[i] == s[N + 1 - i]) cnt++;
}
if(cnt == (N/2)) can_equal = false;
int ans = 0;
for (int i = 1;i < new_s.size();i++) {
ans += (new_s[i] - 'a') * pow (K,M - i) % MOD;
ans %= MOD;
}
ans += (can_equal ? s[M] - 'a' + 1 : s[M] - 'a') % MOD;
ans %= MOD;
std::cout << ans << "\n";
}
signed main () {
int T;
std::cin >> T;
for (int i = 1;i <= T;i++){
std::cout << "Case #" << i << ": ";
solve();
}
return 0;
}
The loophole is the very last moduling forgot:
ans %= MODand of course you can simply useans = (ans + (can_equal ? s[M] - 'a' + 1 : s[M] - 'a')) % MODto avoid this.
Rock Paper Scissors
This one gets really interesting. You need to tell what's hidden in the complex relationships.
Now given that every day is the same (the record is cleared), and the only diff is the $\mathbf{\rho = \frac{W}{E}} = [1,2,10]$, or defined as $0$ when $\mathbf{E} = 0$.
Pick one of those four days and rewrite any round; the friend's odds and the running score follow immediately.
Click any cell to cycle it: R, then P, then S.
So, we may precalculate the ans string (we got four) and return the res based on $\rho$.
Also since every day is the same except the $\rho$, we only care the diff brought by the $\rho$ but not the absolute number of $\mathbf{W}$ (cause it follows a informal distribution and we only care about the average, but the scores of each day is just a linear function of $\mathbf{W}$, Anyway, we do not even care the absolute number of ans, cause it is guaranteed by the problem that there will always be solutions and we are going to find the optimal solutions possible).
How to init then?
We notice that round $a$'s stat depends on the round $(a - 1)$ and that's why we use dp here. [dp refers to dynamic programming]
The state definition and trans formulation:
- state definition: $\mathbf{v[r][p][s]}$
- trans formulation: we define $\mathbf{W_R}$ as the winning possibility if we throw Rock, $\mathbf{E_R}$ as the possibility of getting score $\mathbf{E}$ if we throw Rock, the same to Paper, Scissors $$\mathbf{v}[r][p][s] = max(\mathbf{v}[r - 1][p][s] + W_R + E_R \cdot \rho \ , \mathbf{v}[r][p - 1][s] + W_P + E_P \cdot \rho \ , \\ \mathbf{v}[r][p][s - 1]) + W_S + E_S$$ while here $W_R = \frac{p}{r + p + s - 1}$ and $E_R = \frac{s}{r + p + s - 1}$ the same to Paper, Scissors.
Notice that while $r + p + s = 1$, there are no state before and we need to init three states: $v[1][0][0]$, $v[0][1][0]$ and $v[0][0][1]$.
That's it ! But how do we get optimal string after this?
Can we calculate forward like how we calculate dp?
We can definitely not. That is, we can not travel from index 1 to index 60 while comparing which one is the biggest cause it is wasting the fruit of dp, you are not even using it !
We need to calculate backward, that is: assume that we've got one current status, and we look backward to choose the best string (we know the best ans though).
Assume that we've got one status in the string of the best score, 39th char for example, we then goes back to 38, to see, which state can generate 39th's state (three in total) and get the maximum score among them, that's the char we want that can get the maximum score.
The res is guaranteed to be the optimal cause we always choose the one that can get the optimal score from round 1 to the round of current.
The loophole is that do not forget to work out the score of 39th round (you need to plus $v[38]$ with 39th score to rank).
Anyway, code explains everything:
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
const int MAXM = 61;
double v[MAXM][MAXM][MAXM]; // r p s ,respectively
double sets[4] = {1,0.5,0.1,0};
std::vector<std::string> ans;
void init() {
ans.resize(4);
for (int iter = 0;iter < 4;iter++) {
double rha = sets[iter];
v[0][1][0] = v[0][0][1] = v[1][0][0] = 1/(double)3 + rha * (1/(double)3);
for (int i = 2;i <= 60;i++) {
for (int r = 0;r <= i;r++) {
for (int p = 0;p <= i - r;p++) {
if(r >= 1) v[r][p][i - r - p] = std::max(v[r][p][i - r - p],v[r - 1][p][i - r - p] + p/(double)(i - 1) + rha * ((i - p - r) /(double)(i - 1)));
if(p >= 1) v[r][p][i - r - p] = std::max(v[r][p][i - r - p],v[r][p - 1][i - r - p] + (i - p - r) / (double)(i - 1) + rha * (r/(double)(i - 1)));
if(i - p - r >= 1) v[r][p][i - r - p] = std::max(v[r][p][i - r - p],v[r][p][i - r - p - 1] + r/(double)(i - 1) + rha * (p/(double)(i - 1)));
}
}
}
int cur_rock = 0, cur_paper = 0,cur_sci = 0;
double maximum = -1;
for (int i = 0;i <= 60;i++) {
for (int j = 0;j <= 60 - i;j++) {
if(v[i][j][60 - i - j] > maximum) {
maximum = v[i][j][60 - i - j];
cur_rock = i;
cur_paper = j;
cur_sci = 60 - i - j;
}
}
}
int total = 60;
int* arr[3] = {&cur_rock,&cur_paper,&cur_sci};
char RPC[3] = {'R','P','S'};
while(true) {
if(total == 1) {
int id = cur_rock ? 0 : cur_paper ? 1 : cur_sci ? 2 : -1;
if(id != -1) ans[iter] += RPC[id];
break;
}
int id = -1;
double maximum = 0;
std::vector<double> tmp(3,-1);
if(cur_rock >= 1) tmp[0] = v[cur_rock - 1][cur_paper][cur_sci] + cur_paper/(double)(total - 1) + rha * ((cur_sci) /(double)(total - 1));
if(cur_paper >= 1) tmp[1] = v[cur_rock][cur_paper - 1][cur_sci] + (cur_sci)/(double)(total - 1) + rha * (cur_rock) / (double)(total - 1);
if(cur_sci >= 1) tmp[2] = v[cur_rock][cur_paper][cur_sci - 1] + (cur_rock)/(double)(total - 1) + rha * (cur_paper) / (double)(total - 1);
for (int k = 0;k <= 2;k++) {
if(tmp[k] > maximum) {
maximum = tmp[k];
id = k;
}
}
if(id != -1){
(*arr[id])--;
ans[iter] += RPC[id];
}
total--;
}
for (int i = 0;i <= 60;i++) {
for (int j = 0;j <= 60;j++) {
std::fill(v[i][j],v[i][j] + 61,0);
}
}
}
for (int i = 0;i < 4;i++) {
std::reverse(ans[i].begin(),ans[i].end());
}
}
void solve() {
int W ,E;
std::cin >> W >> E;
if (W == E) {
std::cout << ans[0] << "\n";
} else if (W == 2 * E) {
std::cout << ans[1] << "\n";
} else if (W == 10 * E) {
std::cout << ans[2] << "\n";
} else if (!E) {
std::cout << ans[3] << "\n";
}
}
int main () {
int T,X;
std::cin >> T >> X;
init();
for (int i = 1;i <= T;i++) {
std::cout << "Case #" << i << ": ";
solve();
}
return 0;
}
Yes, we got static ans, and to make your code shorter, you can even try this:
#include <iostream>
int X;
void solve() {
int W, E;
std::cin >> W >> E;
if (W == E) std::cout << "RPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPSRPS" << "\n";
else if (W == 2 * E) std::cout << "RSSPPPPRRRRRRRRSSSSSSSSSSSSSSSSPPPPPPPPPPPPPPPPPPPRRRRRRRRRR" << "\n";
else if (W == 10 * E) std::cout << "RSSSSPPPPPPPPPPPPPPPRRRRRRRRRRRRRRRRRRRRRRRRRSSSSSSSSSSSSSSS" << "\n";
else if (E == 0) std::cout << "RSSSSSSSSSPPPPPPPPPPPPPPPPPPPPPPPPPPPRRRRRRRRRRRRRRRRRRRRRRR" << "\n";
}
int main() {
int T;
std::cin >> T;
std::cin >> X;
for (int i = 1; i <= T; i++) {
std::cout << "Case #" << i << ": ";
solve();
}
}
Which the same gets an AC on https://www.luogu.com.cn/problem/P16847.
Binary Operator
The total function must have shocked you. But you can find hashing after you calm down.
How to hash? We only need to hash $\mathbf{A\#B}$, that is we may need to calculate the numbers computable and try to simplify the expression to the fullest.
So, my method is to use random ID (at a range of $2^{64}$), using MOD big enough to avoid possible conflicts (I can not even use $998,244,353$, too small that's why).
So I use $2^{61} - 1$ as the MOD. Every time we meet $\mathbf{A\#B}$, we give it an ID and use it as a number value to work with directly and finally we get a number to identify and count equivalence classes.
The problem left is how to simplify, using Reverse Polish Notation / Postfix notation? That is not workable and too complex.
This problem actually do not want you to use the trick of Reverse Polish Notation, it works though. Why not use a tree-recursive computing? It is a binary tree: $\mathbf{((EXPRESSION) \ OPERATOR \ (EXPRESSION))}$, you can always expand to the next level if possible (not a number).
That's all, code here:
#include <iostream>
#include <vector>
#include <map>
#include <random>
#include <cstdint>
#define int long long
const int MOD = (1ULL<<61) - 1;
const int MAXM = 105;
std::map<std::pair<int,int>,int> hash_table;
uint64_t random_uint64() {
static std::mt19937_64 rng(std::random_device{}());
static std::uniform_int_distribution<uint64_t> dist(
0, std::numeric_limits<uint64_t>::max()
);
return dist(rng) % MOD;
}
int get_random_ID_and_mark (int L,int R) {
if(hash_table.find(std::make_pair(L,R)) == hash_table.end()) {
int val = random_uint64();
hash_table.insert({std::make_pair(L,R),val});
return val;
} else return hash_table[std::make_pair(L,R)];
}
int eval(std::string str) {
if(str[0] != '(') {
int ans = 0;
for (int i = 0;i < str.length();i++) {
ans = ((__int128_t)10 * ans + (str[i] - '0')) % MOD;
}
return ans;
}
int left_parentheses = 0;
int right_parentheses = 0;
char _operator;
int dividing_index;
for (int i = 0;i < str.length();i++) {
char c = str[i];
if (c == '(') left_parentheses++;
else if(c == ')') right_parentheses++;
else if (c == '*' || c == '+' || c == '#') {
if(left_parentheses == right_parentheses + 1) {
_operator = c;
dividing_index = i;
break;
}
}
}
std::string left_str = str.substr(1, dividing_index - 1);
std::string right_str = str.substr(dividing_index + 1, str.size() - dividing_index - 2);
int L = eval(left_str);
int R = eval(right_str);
if(_operator == '+') return (L + R) % MOD;
else if (_operator == '*') return((__int128_t)L * R) % MOD;
else if (_operator == '#') return get_random_ID_and_mark(L,R);
}
void solve() {
int N;
std::cin >> N;
hash_table.clear();
std::vector<std::string> str;
str.resize(N + 1);
for (int i = 1;i <= N;i++) {
std::cin >> str[i];
}
std::vector<int> hashing;
hashing.resize(101);
std::map<int,int> maps;
int cnt = 1;
for (int i = 1;i <= N;i++) {
hashing[i] = eval(str[i]);
if(maps.find(hashing[i]) == maps.end()) {
maps.insert({hashing[i],cnt});
cnt++;
}
}
for (int i = 1;i <= N;i++) {
std::cout << maps[hashing[i]] << " ";
}
std::cout << "\n";
}
signed main () {
int T;
std::cin >>T;
for (int i = 1;i <= T;i++) {
std::cout << "Case #" << i << ": ";
solve();
}
}
My method is the alternative method mentioned in the official analysis.
The main method is to simply to a form like $\mathbf{(A\#B) * C + D}$ and get a tuple $(A,B,C,D)$ and "We can then use a hashtable or any similar data structure to categorize them into different equivalence classes".
However, they did not mention the hashing method. Also, I think it failed to consider the case of two of $A, B, C, D$ are equal and the identity between $\mathbf{(A\#B) * C + D}$ and $\mathbf{(D + C * (A\#B))}$, they are the same but generate diff tuple representation.
But as mentioned here "Unfortunately, we do not have a simple proof that such solution has sufficiently small probability of failure. To further decrease the probability of false matches, the process can be repeated several times, putting two expressions into the same class only if their evaluations matched every time.", that's why I use a modulus big enough.
Emm, But I indeed want a method at the accuracy of 100% ... TO BE CONTINUED
Comments